package leetcode.day_2020_2021_2_1_2021_2_7;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 22. 括号生成
 * https://leetcode-cn.com/problems/generate-parentheses/
 */
public class LeetCode0022 {
    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }

    /**
     * 深度优先遍历
     * @param n
     * @return
     */
    public static List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n == 0) return res;
        dfs("", n, n, res);
        return res;
    }

    public static void dfs(String str, int left, int right, List<String> res) {
        if (left==0 && right==0) {
            res.add(str);
            return;
        }

        if(left > right) {
            return;
        }

        if(left > 0) {
            dfs(str+"(", left-1, right, res);
        }

        if(right > 0) {
            dfs(str+")", left, right-1, res);
        }
    }
}
